#include "binarytreewindow.h"
#include <QPainter>
#include <QDialog>
#include <QDialogButtonBox>
#include <QVBoxLayout>
#include <QFormLayout>
#include <QTime>
#include <cmath>
#include <functional>

// 替换std::max的数学函数
double my_atan2(double y, double x) {
    return atan2(y, x);
}

double my_cos(double x) {
    return cos(x);
}

double my_sin(double x) {
    return sin(x);
}

// TreeVisualizationWidget 的实现
int TreeVisualizationWidget::getTreeHeight(TreeNode* node) {
    if (node == nullptr) return 0;
    int leftHeight = getTreeHeight(node->left);
    int rightHeight = getTreeHeight(node->right);
    return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}

int TreeVisualizationWidget::getTreeWidth(TreeNode* node) {
    if (node == nullptr) return 0;

    int maxWidth = 0;
    calculateSubtreeWidth(node, 0, maxWidth);
    return maxWidth;
}

void TreeVisualizationWidget::calculateSubtreeWidth(TreeNode* node, int level, int& maxWidth) {
    if (node == nullptr) return;

    // 计算当前层的宽度
    int currentWidth = (1 << level); // 2^level
    if (currentWidth > maxWidth) {
        maxWidth = currentWidth;
    }

    calculateSubtreeWidth(node->left, level + 1, maxWidth);
    calculateSubtreeWidth(node->right, level + 1, maxWidth);
}

void TreeVisualizationWidget::calculateTreeDimensions() {
    if (root == nullptr) {
        m_treeWidth = 1200;
        m_treeHeight = 700;
        return;
    }

    int height = getTreeHeight(root);
    int width = getTreeWidth(root);

    // 根据树的高度和宽度计算合适的尺寸
    m_treeWidth = width * 300 + 600;
    m_treeHeight = height * 200 + 300;

    // 设置最小尺寸
    if (m_treeWidth < 1200) m_treeWidth = 1200;
    if (m_treeHeight < 700) m_treeHeight = 700;

    // 重新计算widget尺寸
    setFixedSize(m_treeWidth, m_treeHeight);

    // 计算所有节点的位置
    calculateNodePositions();
}

void TreeVisualizationWidget::calculateNodePositions() {
    if (root == nullptr) return;

    // 清空之前的节点位置信息
    m_nodePositionsX.clear();
    m_nodePositionsY.clear();

    // 使用队列进行层次遍历，确保节点位置正确
    const int MAX_NODES = 1000;
    if (m_nodePointers != nullptr) {
        delete[] m_nodePointers;
    }
    m_nodePointers = new TreeNode*[MAX_NODES];
    m_nodeCount = 0;

    // 使用队列进行层次遍历
    TreeNodeQueue q;
    IntArray nodeLevels; // 存储每个节点的层级
    IntArray parentIndices; // 存储每个节点的父节点索引

    q.push(root);
    nodeLevels.push_back(0);
    parentIndices.push_back(-1); // 根节点没有父节点

    while (!q.empty() && m_nodeCount < MAX_NODES) {
        TreeNode* current = q.front();
        int level = nodeLevels.front();
        int parentIndex = parentIndices.front();

        q.pop();
        nodeLevels.pop_front();
        parentIndices.pop_front();

        // 计算当前节点的位置
        int x, y;

        if (parentIndex == -1) {
            // 根节点在中间
            x = m_treeWidth / 2;
            y = 50;
        } else {
            // 根据父节点位置计算当前节点位置
            int parentX = m_nodePositionsX[parentIndex];
            int parentY = m_nodePositionsY[parentIndex];

            // 计算水平偏移
            int horizontalOffset = m_treeWidth / (1 << (level + 1));

            // 确定是左孩子还是右孩子
            TreeNode* parent = m_nodePointers[parentIndex];
            if (parent->left == current) {
                // 左孩子在父节点左侧
                x = parentX - horizontalOffset;
            } else {
                // 右孩子在父节点右侧
                x = parentX + horizontalOffset;
            }

            y = parentY + 150; // 垂直间距
        }

        // 存储节点位置
        m_nodePositionsX.push_back(x);
        m_nodePositionsY.push_back(y);
        m_nodePointers[m_nodeCount] = current;

        // 记录当前节点的索引，用于其子节点的计算
        int currentIndex = m_nodeCount;
        m_nodeCount++;

        // 添加子节点到队列
        if (current->left != nullptr) {
            q.push(current->left);
            nodeLevels.push_back(level + 1);
            parentIndices.push_back(currentIndex);
        }

        if (current->right != nullptr) {
            q.push(current->right);
            nodeLevels.push_back(level + 1);
            parentIndices.push_back(currentIndex);
        }
    }
}

QPoint TreeVisualizationWidget::getCurrentTraverseNodePosition() const
{
    if (m_currentTraverseNodeIndex == -1) return QPoint();

    return QPoint(m_nodePositionsX[m_currentTraverseNodeIndex],
                  m_nodePositionsY[m_currentTraverseNodeIndex]);
}

void TreeVisualizationWidget::startTraversal(const QVector<TreeNode*>& order) {
    m_traverseOrder = order;
    m_currentTraverseIndex = 0;
    m_currentTraverseNode = nullptr;
    m_currentTraverseNodeIndex = -1;
    update();
}

void TreeVisualizationWidget::nextTraversalStep() {
    if (m_currentTraverseIndex < m_traverseOrder.size()) {
        m_currentTraverseNode = m_traverseOrder[m_currentTraverseIndex];

        // 找到当前节点在节点数组中的索引
        m_currentTraverseNodeIndex = -1;
        for (int i = 0; i < m_nodeCount; i++) {
            if (m_nodePointers[i] == m_currentTraverseNode) {
                m_currentTraverseNodeIndex = i;
                break;
            }
        }

        m_currentTraverseIndex++;
        update();

        // 发出信号，传递当前遍历结果
        QString result;
        for (int i = 0; i < m_currentTraverseIndex; i++) {
            if (i > 0) result += " ";
            result += QString::number(m_traverseOrder[i]->data);
        }
        emit traversalStepCompleted(result);
    }
}

void TreeVisualizationWidget::resetTraversal() {
    m_currentTraverseNode = nullptr;
    m_currentTraverseNodeIndex = -1;
    m_traverseOrder.clear();
    m_currentTraverseIndex = -1;
    update();
}

void TreeVisualizationWidget::paintEvent(QPaintEvent* event)
{
    Q_UNUSED(event);

    QPainter painter(this);
    painter.setRenderHint(QPainter::Antialiasing);
    painter.setPen(QPen(Qt::black, 2));

    QFont font = painter.font();
    font.setPointSize(10);
    painter.setFont(font);

    painter.fillRect(rect(), Qt::white);

    if (root == nullptr) {
        painter.drawText(rect(), Qt::AlignCenter, "二叉树为空");
        return;
    }

    drawTree(painter);
}

void TreeVisualizationWidget::drawTree(QPainter& painter)
{
    // 首先绘制所有连线
    for (int i = 0; i < m_nodeCount; i++) {
        TreeNode* node = m_nodePointers[i];
        int x = m_nodePositionsX[i];
        int y = m_nodePositionsY[i];

        // 查找左子节点的位置
        if (node->left != nullptr) {
            for (int j = 0; j < m_nodeCount; j++) {
                if (m_nodePointers[j] == node->left) {
                    int childX = m_nodePositionsX[j];
                    int childY = m_nodePositionsY[j];
                    painter.setPen(QPen(Qt::blue, 2));

                    // 从当前节点的左连接点指向子节点的连接点
                    int startX = x - 60;  // 左连接点中心
                    int startY = y + 25;  // 左连接点中心
                    int endX = childX;    // 子节点中心X
                    int endY = childY - 25; // 子节点顶部

                    drawPointerLine(painter, startX, startY, endX, endY);
                    break;
                }
            }
        } else {
            // NULL指针：从节点外框左侧的连接点中心引出
            painter.setPen(QPen(Qt::red, 2));
            int startX = x - 60;  // 左连接点中心
            int startY = y + 25;  // 左连接点中心
            drawNullPointer(painter, startX, startY, true);
        }

        // 查找右子节点的位置
        if (node->right != nullptr) {
            for (int j = 0; j < m_nodeCount; j++) {
                if (m_nodePointers[j] == node->right) {
                    int childX = m_nodePositionsX[j];
                    int childY = m_nodePositionsY[j];
                    painter.setPen(QPen(Qt::blue, 2));

                    // 从当前节点的右连接点指向子节点的连接点
                    int startX = x + 60;  // 右连接点中心
                    int startY = y + 25;  // 右连接点中心
                    int endX = childX;    // 子节点中心X
                    int endY = childY - 25; // 子节点顶部

                    drawPointerLine(painter, startX, startY, endX, endY);
                    break;
                }
            }
        } else {
            // NULL指针：从节点外框右侧的连接点中心引出
            painter.setPen(QPen(Qt::red, 2));
            int startX = x + 60;  // 右连接点中心
            int startY = y + 25;  // 右连接点中心
            drawNullPointer(painter, startX, startY, false);
        }
    }

    // 然后绘制所有节点（避免连线覆盖节点）
    for (int i = 0; i < m_nodeCount; i++) {
        TreeNode* node = m_nodePointers[i];
        int x = m_nodePositionsX[i];
        int y = m_nodePositionsY[i];
        drawThreeCellNode(painter, node, x, y);
    }
}

void TreeVisualizationWidget::drawThreeCellNode(QPainter& painter, TreeNode* node, int x, int y)
{
    // 设置节点样式
    painter.setPen(QPen(Qt::black, 2));

    // 如果是当前遍历的节点，用高亮颜色
    if (node == m_currentTraverseNode) {
        painter.setBrush(QBrush(QColor(255, 255, 0))); // 黄色高亮
    } else {
        painter.setBrush(QBrush(Qt::white));
    }

    // 绘制节点外框（三个格子）
    QRect nodeRect(x - 60, y, 120, 50);
    painter.drawRect(nodeRect);

    // 绘制内部垂直线分隔三个区域
    painter.drawLine(x - 20, y, x - 20, y + 50);  // 左分隔线
    painter.drawLine(x + 20, y, x + 20, y + 50);  // 右分隔线

    // 绘制三个区域的内容
    QFont font = painter.font();
    font.setPointSize(9);
    painter.setFont(font);

    // 左格子：Lchild
    QRect leftRect(x - 60, y, 40, 50);
    painter.drawText(leftRect, Qt::AlignCenter, "Lchild");

    // 中格子：data
    QRect middleRect(x - 20, y, 40, 50);
    painter.setBrush(QBrush(Qt::lightGray));
    painter.drawRect(middleRect);
    painter.setBrush(QBrush(Qt::white));
    painter.drawText(middleRect, Qt::AlignCenter, QString::number(node->data));

    // 右格子：Rchild
    QRect rightRect(x + 20, y, 40, 50);
    painter.drawText(rightRect, Qt::AlignCenter, "Rchild");

    // 绘制指针连接点 - 位于节点外框上
    painter.setBrush(QBrush(Qt::blue));

    // 左指针连接点 - 位于节点外框左侧中心
    painter.drawEllipse(x - 60 - 3, y + 25 - 3, 6, 6);

    // 右指针连接点 - 位于节点外框右侧中心
    painter.drawEllipse(x + 60 - 3, y + 25 - 3, 6, 6);

    // 恢复字体大小
    font.setPointSize(10);
    painter.setFont(font);
}

void TreeVisualizationWidget::drawPointerLine(QPainter& painter, int startX, int startY, int endX, int endY)
{
    // 绘制连线
    painter.drawLine(startX, startY, endX, endY);

    // 计算箭头方向
    double angle = my_atan2(endY - startY, endX - startX);

    // 绘制箭头
    int arrowSize = 8;
    QPointF arrowP1 = QPointF(endX - arrowSize * my_cos(angle + M_PI/6),
                              endY - arrowSize * my_sin(angle + M_PI/6));
    QPointF arrowP2 = QPointF(endX - arrowSize * my_cos(angle - M_PI/6),
                              endY - arrowSize * my_sin(angle - M_PI/6));

    QPolygonF arrowHead;
    arrowHead << QPointF(endX, endY) << arrowP1 << arrowP2;

    painter.setBrush(QBrush(Qt::blue));
    painter.drawPolygon(arrowHead);
}

void TreeVisualizationWidget::drawNullPointer(QPainter& painter, int startX, int startY, bool isLeft)
{
    // 计算NULL指针的方向和长度
    int nullPointerLength = 40;
    int endX, endY;

    if (isLeft) {
        endX = startX - nullPointerLength;
        endY = startY + 20;
    } else {
        endX = startX + nullPointerLength;
        endY = startY + 20;
    }

    // 绘制指向NULL的线段
    painter.drawLine(startX, startY, endX, endY);

    // 绘制箭头
    double angle = my_atan2(endY - startY, endX - startX);
    int arrowSize = 8;
    QPointF arrowP1 = QPointF(endX - arrowSize * my_cos(angle + M_PI/6),
                              endY - arrowSize * my_sin(angle + M_PI/6));
    QPointF arrowP2 = QPointF(endX - arrowSize * my_cos(angle - M_PI/6),
                              endY - arrowSize * my_sin(angle - M_PI/6));

    QPolygonF arrowHead;
    arrowHead << QPointF(endX, endY) << arrowP1 << arrowP2;

    painter.setBrush(QBrush(Qt::red));
    painter.drawPolygon(arrowHead);

    // 绘制NULL文本
    painter.setPen(Qt::red);
    QFont font = painter.font();
    font.setPointSize(8);
    painter.setFont(font);

    if (isLeft) {
        painter.drawText(endX - 25, endY + 15, "NULL");
    } else {
        painter.drawText(endX + 5, endY + 15, "NULL");
    }

    painter.setPen(Qt::black);
    font.setPointSize(10);
    painter.setFont(font);
}

// BinaryTreeWindow 的实现
BinaryTreeWindow::BinaryTreeWindow(QWidget *parent)
    : QMainWindow(parent), m_root(nullptr), m_size(0), m_isTraversing(false), m_traverseSpeed(800)
{
    setupUI();
    updateDisplay();

    // 初始化遍历定时器
    m_traverseTimer = new QTimer(this);
    connect(m_traverseTimer, &QTimer::timeout, this, [this]() {
        if (m_visualizationWidget->isTraversing()) {
            m_visualizationWidget->nextTraversalStep();
        } else {
            m_traverseTimer->stop();
            m_isTraversing = false;
            // 遍历完成后更新显示完整信息
            updateDisplay();
        }
    });
}

BinaryTreeWindow::~BinaryTreeWindow()
{
    clearTree(m_root);
}

void BinaryTreeWindow::scrollToNodePosition(const QPoint& nodePos)
{
    if (nodePos.isNull()) return;

    // 计算要滚动到的位置
    // 节点位置是节点中心的坐标，我们希望节点在视口中央
    int targetX = nodePos.x() - m_scrollArea->viewport()->width() / 2;
    int targetY = nodePos.y() - m_scrollArea->viewport()->height() / 2;

    // 确保滚动位置在有效范围内
    targetX = qMax(0, qMin(targetX, m_scrollArea->horizontalScrollBar()->maximum()));
    targetY = qMax(0, qMin(targetY, m_scrollArea->verticalScrollBar()->maximum()));

    // 设置滚动条位置
    m_scrollArea->horizontalScrollBar()->setValue(targetX);
    m_scrollArea->verticalScrollBar()->setValue(targetY);
}

void BinaryTreeWindow::setupUI()
{
    setWindowTitle("二叉树可视化演示");
    setMinimumSize(1200, 700);
    resize(1200, 700);

    QWidget *centralWidget = new QWidget(this);
    setCentralWidget(centralWidget);

    QHBoxLayout *mainLayout = new QHBoxLayout(centralWidget);

    // 左侧：可视化部分 - 使用滚动区域
    QVBoxLayout *leftLayout = new QVBoxLayout();
    QLabel *visualLabel = new QLabel("二叉树可视化:");
    visualLabel->setStyleSheet("font-weight: bold; font-size: 14px;");

    // 创建滚动区域
    m_scrollArea = new QScrollArea();
    m_scrollArea->setWidgetResizable(true);
    m_scrollArea->setHorizontalScrollBarPolicy(Qt::ScrollBarAsNeeded);
    m_scrollArea->setVerticalScrollBarPolicy(Qt::ScrollBarAsNeeded);
    m_scrollArea->setMinimumSize(900, 650);

    // 创建可视化部件
    m_visualizationWidget = new TreeVisualizationWidget();
    connect(m_visualizationWidget, &TreeVisualizationWidget::traversalStepCompleted,
            this, &BinaryTreeWindow::onTraversalStepCompleted);
    m_scrollArea->setWidget(m_visualizationWidget);

    leftLayout->addWidget(visualLabel);
    leftLayout->addWidget(m_scrollArea);
    mainLayout->addLayout(leftLayout, 3);

    // 右侧：操作和信息部分
    QVBoxLayout *rightLayout = new QVBoxLayout();
    rightLayout->setSpacing(15);

    QWidget *rightPanel = new QWidget();
    rightPanel->setLayout(rightLayout);
    rightPanel->setMaximumWidth(300);

    // 返回按钮
    QPushButton *returnBtn = new QPushButton("返回主菜单");
    returnBtn->setStyleSheet("QPushButton { background-color: #f0f0f0; border: 1px solid #ccc; padding: 8px; }");
    rightLayout->addWidget(returnBtn);

    // 操作按钮组
    QGroupBox *opsGroup = new QGroupBox("操作面板");
    opsGroup->setStyleSheet("QGroupBox { font-weight: bold; }");
    QVBoxLayout *opsLayout = new QVBoxLayout(opsGroup);
    opsLayout->setSpacing(10);

    // 初始化数据按钮
    QPushButton *inputBtn = new QPushButton("构建二叉树");
    inputBtn->setToolTip("点击输入层次遍历序列构建二叉树");
    inputBtn->setMinimumHeight(35);

    // 插入节点按钮
    QPushButton *insertBtn = new QPushButton("插入节点");
    insertBtn->setToolTip("点击输入要插入的值");
    insertBtn->setMinimumHeight(35);

    // 遍历操作
    QGroupBox *traverseGroup = new QGroupBox("遍历操作");
    QVBoxLayout *traverseLayout = new QVBoxLayout(traverseGroup);
    m_traverseCombo = new QComboBox();
    m_traverseCombo->addItem("前序遍历");
    m_traverseCombo->addItem("中序遍历");
    m_traverseCombo->addItem("后序遍历");
    m_traverseCombo->addItem("层次遍历");

    // 遍历速度控制
    QHBoxLayout *speedLayout = new QHBoxLayout();
    QLabel *speedLabel = new QLabel("速度:");
    QComboBox *speedCombo = new QComboBox();
    speedCombo->addItem("慢速", 1500);
    speedCombo->addItem("中速", 800);
    speedCombo->addItem("快速", 400);
    speedCombo->setCurrentIndex(1); // 默认中速

    // 连接速度选择信号
    connect(speedCombo, QOverload<int>::of(&QComboBox::currentIndexChanged), [this, speedCombo](int index) {
        m_traverseSpeed = speedCombo->itemData(index).toInt();
        if (m_isTraversing) {
            m_traverseTimer->stop();
            m_traverseTimer->start(m_traverseSpeed);
        }
    });

    speedLayout->addWidget(speedLabel);
    speedLayout->addWidget(speedCombo);

    QPushButton *traverseBtn = new QPushButton("执行遍历");
    traverseBtn->setMinimumHeight(35);

    traverseLayout->addWidget(m_traverseCombo);
    traverseLayout->addLayout(speedLayout);
    traverseLayout->addWidget(traverseBtn);

    // 其他操作按钮
    QPushButton *clearBtn = new QPushButton("清空二叉树");
    clearBtn->setMinimumHeight(35);
    QPushButton *randomBtn = new QPushButton("生成随机二叉树");
    randomBtn->setMinimumHeight(35);

    // 将所有按钮添加到操作面板
    opsLayout->addWidget(inputBtn);
    opsLayout->addWidget(insertBtn);
    opsLayout->addWidget(traverseGroup);

    QHBoxLayout *otherOpsLayout = new QHBoxLayout();
    otherOpsLayout->addWidget(clearBtn);
    otherOpsLayout->addWidget(randomBtn);
    opsLayout->addLayout(otherOpsLayout);

    // 信息显示部分
    QGroupBox *infoGroup = new QGroupBox("二叉树信息");
    infoGroup->setStyleSheet("QGroupBox { font-weight: bold; }");
    QVBoxLayout *infoLayout = new QVBoxLayout(infoGroup);
    m_display = new QTextEdit();
    m_display->setReadOnly(true);
    m_display->setMaximumHeight(400);
    infoLayout->addWidget(m_display);

    // 将操作面板和信息显示添加到右侧布局
    rightLayout->addWidget(opsGroup);
    rightLayout->addWidget(infoGroup);

    // 添加右侧面板到主布局
    mainLayout->addWidget(rightPanel, 1);

    // 连接信号槽
    connect(inputBtn, &QPushButton::clicked, this, &BinaryTreeWindow::onInputData);
    connect(insertBtn, &QPushButton::clicked, this, &BinaryTreeWindow::onInsert);
    connect(traverseBtn, &QPushButton::clicked, this, &BinaryTreeWindow::onTraverse);
    connect(clearBtn, &QPushButton::clicked, this, &BinaryTreeWindow::onClear);
    connect(randomBtn, &QPushButton::clicked, this, &BinaryTreeWindow::onGenerateRandom);
    connect(returnBtn, &QPushButton::clicked, this, &BinaryTreeWindow::onReturnToMainMenu);
}

void BinaryTreeWindow::onReturnToMainMenu()
{
    emit returnToMainMenu();
    this->close();
}

void BinaryTreeWindow::updateDisplay()
{
    QString info = QString("二叉树信息\n\n节点数: %1\n\n").arg(m_size);

    if (m_root == nullptr) {
        info += "二叉树为空";
    } else {
        info += "层次遍历结果: ";
        QString levelOrder;
        QVector<TreeNode*> levelOrderNodes;
        levelOrderTraversal(m_root, levelOrderNodes);
        for (TreeNode* node : levelOrderNodes) {
            levelOrder += QString::number(node->data) + " ";
        }
        info += levelOrder + "\n\n";

        info += "树的高度: " + QString::number(getTreeHeight(m_root)) + "\n\n";

        info += "前序遍历: ";
        QString preorder;
        QVector<TreeNode*> preorderNodes;
        preorderTraversal(m_root, preorderNodes);
        for (TreeNode* node : preorderNodes) {
            preorder += QString::number(node->data) + " ";
        }
        info += preorder + "\n\n";

        info += "中序遍历: ";
        QString inorder;
        QVector<TreeNode*> inorderNodes;
        inorderTraversal(m_root, inorderNodes);
        for (TreeNode* node : inorderNodes) {
            inorder += QString::number(node->data) + " ";
        }
        info += inorder + "\n\n";

        info += "后序遍历: ";
        QString postorder;
        QVector<TreeNode*> postorderNodes;
        postorderTraversal(m_root, postorderNodes);
        for (TreeNode* node : postorderNodes) {
            postorder += QString::number(node->data) + " ";
        }
        info += postorder;

        // 如果正在遍历，显示当前遍历结果
        if (m_isTraversing) {
            info += "\n\n=== 当前遍历过程 ===\n";
            info += m_currentTraverseResult;
        }
    }

    m_display->setText(info);
    m_visualizationWidget->setRoot(m_root);

    // 自动滚动到树的中部
    QSize treeSize = m_visualizationWidget->getTreeSize();
    if (treeSize.width() > m_scrollArea->width()) {
        m_scrollArea->horizontalScrollBar()->setValue(treeSize.width() / 2 - m_scrollArea->width() / 2);
    }
}

void BinaryTreeWindow::clearTree(TreeNode* node)
{
    if (node == nullptr) return;
    clearTree(node->left);
    clearTree(node->right);
    delete node;
}

void BinaryTreeWindow::preorderTraversal(TreeNode* node, QVector<TreeNode*>& result)
{
    if (node == nullptr) return;
    result.push_back(node);
    preorderTraversal(node->left, result);
    preorderTraversal(node->right, result);
}

void BinaryTreeWindow::inorderTraversal(TreeNode* node, QVector<TreeNode*>& result)
{
    if (node == nullptr) return;
    inorderTraversal(node->left, result);
    result.push_back(node);
    inorderTraversal(node->right, result);
}

void BinaryTreeWindow::postorderTraversal(TreeNode* node, QVector<TreeNode*>& result)
{
    if (node == nullptr) return;
    postorderTraversal(node->left, result);
    postorderTraversal(node->right, result);
    result.push_back(node);
}

void BinaryTreeWindow::levelOrderTraversal(TreeNode* node, QVector<TreeNode*>& result)
{
    if (node == nullptr) return;

    TreeNodeQueue q;
    q.push(node);

    while (!q.empty()) {
        TreeNode* current = q.front();
        q.pop();
        result.push_back(current);

        if (current->left != nullptr) q.push(current->left);
        if (current->right != nullptr) q.push(current->right);
    }
}

TreeNode* BinaryTreeWindow::buildTreeFromLevelOrder(const IntArray& values)
{
    if (values.empty()) return nullptr;

    TreeNode* root = new TreeNode(values[0]);
    TreeNodeQueue q;
    q.push(root);

    int i = 1;
    while (!q.empty() && i < values.size()) {
        TreeNode* current = q.front();
        q.pop();

        if (i < values.size()) {
            current->left = new TreeNode(values[i]);
            q.push(current->left);
        }
        i++;

        if (i < values.size()) {
            current->right = new TreeNode(values[i]);
            q.push(current->right);
        }
        i++;
    }

    return root;
}

int BinaryTreeWindow::getTreeHeight(TreeNode* node)
{
    if (node == nullptr) return 0;
    int leftHeight = getTreeHeight(node->left);
    int rightHeight = getTreeHeight(node->right);
    return 1 + max(leftHeight, rightHeight);
}

int BinaryTreeWindow::randomInt(int min, int max)
{
    static bool seeded = false;
    if (!seeded) {
        srand(QTime::currentTime().msec());
        seeded = true;
    }
    return min + (rand() % (max - min + 1));
}

void BinaryTreeWindow::onTraversalStepCompleted(const QString& currentResult)
{
    m_currentTraverseResult = currentResult;
    updateDisplay();

    // 获取当前遍历节点的位置并滚动到该位置
    QPoint nodePos = m_visualizationWidget->getCurrentTraverseNodePosition();
    if (!nodePos.isNull()) {
        scrollToNodePosition(nodePos);
    }
}

void BinaryTreeWindow::onInputData()
{
    QDialog dialog(this);
    dialog.setWindowTitle("构建二叉树");
    dialog.setFixedSize(400, 150);

    QVBoxLayout *mainLayout = new QVBoxLayout(&dialog);

    QLabel *label = new QLabel("请输入层次遍历序列（用空格分隔）:");
    QLineEdit *edit = new QLineEdit();
    edit->setPlaceholderText("例如: 1 2 3 4 5");

    QDialogButtonBox *buttons = new QDialogButtonBox(QDialogButtonBox::Ok | QDialogButtonBox::Cancel);

    mainLayout->addWidget(label);
    mainLayout->addWidget(edit);
    mainLayout->addWidget(buttons);

    connect(buttons, &QDialogButtonBox::accepted, &dialog, &QDialog::accept);
    connect(buttons, &QDialogButtonBox::rejected, &dialog, &QDialog::reject);

    if (dialog.exec() == QDialog::Accepted) {
        QString input = edit->text();
        if (input.isEmpty()) {
            QMessageBox::warning(this, "输入错误", "请输入有效的层次遍历序列");
            return;
        }

        clearTree(m_root);
        m_root = nullptr;
        m_size = 0;

        QStringList numbers = input.split(' ', Qt::SkipEmptyParts);
        IntArray values;

        for (const QString& numStr : numbers) {
            bool ok;
            int value = numStr.toInt(&ok);
            if (ok) {
                values.push_back(value);
            } else {
                QMessageBox::warning(this, "输入错误", QString("'%1' 不是有效的整数").arg(numStr));
                return;
            }
        }

        if (!values.empty()) {
            m_root = buildTreeFromLevelOrder(values);

            TreeNodeQueue q;
            q.push(m_root);
            while (!q.empty()) {
                TreeNode* current = q.front();
                q.pop();
                m_size++;

                if (current->left != nullptr) q.push(current->left);
                if (current->right != nullptr) q.push(current->right);
            }

            updateDisplay();
            QMessageBox::information(this, "构建成功", QString("成功构建包含 %1 个节点的二叉树").arg(m_size));
        } else {
            QMessageBox::warning(this, "输入错误", "请输入有效的整数序列");
        }
    }
}

void BinaryTreeWindow::onInsert()
{
    QDialog dialog(this);
    dialog.setWindowTitle("插入节点");
    dialog.setFixedSize(300, 120);

    QVBoxLayout *mainLayout = new QVBoxLayout(&dialog);

    QLabel *label = new QLabel("请输入要插入的值:");
    QLineEdit *edit = new QLineEdit();
    edit->setPlaceholderText("整数");

    QDialogButtonBox *buttons = new QDialogButtonBox(QDialogButtonBox::Ok | QDialogButtonBox::Cancel);

    mainLayout->addWidget(label);
    mainLayout->addWidget(edit);
    mainLayout->addWidget(buttons);

    connect(buttons, &QDialogButtonBox::accepted, &dialog, &QDialog::accept);
    connect(buttons, &QDialogButtonBox::rejected, &dialog, &QDialog::reject);

    if (dialog.exec() == QDialog::Accepted) {
        QString input = edit->text();
        if (input.isEmpty()) {
            QMessageBox::warning(this, "输入错误", "请输入要插入的值");
            return;
        }

        bool ok;
        int value = input.toInt(&ok);
        if (ok) {
            if (m_root == nullptr) {
                m_root = new TreeNode(value);
                m_size = 1;
            } else {
                TreeNodeQueue q;
                q.push(m_root);

                while (!q.empty()) {
                    TreeNode* current = q.front();
                    q.pop();

                    if (current->left == nullptr) {
                        current->left = new TreeNode(value);
                        m_size++;
                        break;
                    } else {
                        q.push(current->left);
                    }

                    if (current->right == nullptr) {
                        current->right = new TreeNode(value);
                        m_size++;
                        break;
                    } else {
                        q.push(current->right);
                    }
                }
            }

            updateDisplay();
            QMessageBox::information(this, "插入成功", QString("节点 %1 已插入").arg(value));
        } else {
            QMessageBox::warning(this, "输入错误", "请输入有效的整数");
        }
    }
}

void BinaryTreeWindow::onTraverse()
{
    if (m_root == nullptr) {
        QMessageBox::information(this, "遍历结果", "二叉树为空");
        return;
    }

    // 停止之前的遍历
    if (m_isTraversing) {
        m_traverseTimer->stop();
        m_visualizationWidget->resetTraversal();
        m_isTraversing = false;
    }

    QString traverseType = m_traverseCombo->currentText();
    QVector<TreeNode*> traverseOrder;

    if (traverseType == "前序遍历") {
        preorderTraversal(m_root, traverseOrder);
    } else if (traverseType == "中序遍历") {
        inorderTraversal(m_root, traverseOrder);
    } else if (traverseType == "后序遍历") {
        postorderTraversal(m_root, traverseOrder);
    } else if (traverseType == "层次遍历") {
        levelOrderTraversal(m_root, traverseOrder);
    }

    // 开始可视化遍历
    m_isTraversing = true;
    m_currentTraverseResult = "";
    m_visualizationWidget->startTraversal(traverseOrder);
    m_traverseTimer->start(m_traverseSpeed);
}

void BinaryTreeWindow::onClear()
{
    QMessageBox::StandardButton reply;
    reply = QMessageBox::question(this, "确认清空", "确定要清空二叉树吗？",
                                  QMessageBox::Yes | QMessageBox::No);
    if (reply == QMessageBox::Yes) {
        // 停止遍历
        if (m_isTraversing) {
            m_traverseTimer->stop();
            m_visualizationWidget->resetTraversal();
            m_isTraversing = false;
        }

        clearTree(m_root);
        m_root = nullptr;
        m_size = 0;
        updateDisplay();
        QMessageBox::information(this, "清空成功", "二叉树已清空");
    }
}

void BinaryTreeWindow::onGenerateRandom()
{
    QMessageBox::StandardButton reply;
    reply = QMessageBox::question(this, "生成随机二叉树",
                                  "确定要生成随机二叉树吗？这将替换当前二叉树。",
                                  QMessageBox::Yes | QMessageBox::No);
    if (reply == QMessageBox::Yes) {
        // 停止遍历
        if (m_isTraversing) {
            m_traverseTimer->stop();
            m_visualizationWidget->resetTraversal();
            m_isTraversing = false;
        }

        clearTree(m_root);
        m_root = nullptr;
        m_size = 0;

        int nodeCount = randomInt(5, 15); // 增加节点数量以测试滚动功能
        IntArray values;

        for (int i = 0; i < nodeCount; i++) {
            values.push_back(randomInt(1, 100));
        }

        m_root = buildTreeFromLevelOrder(values);
        m_size = nodeCount;

        updateDisplay();
        QMessageBox::information(this, "生成成功", QString("已生成包含 %1 个节点的随机二叉树").arg(nodeCount));
    }
}
